package com.cat.gridChart;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/shortest-bridge/description/
 * @create 2025/9/7 20:49
 * @since JDK17
 */

public class Solution16 {
    int n, m, t, h, ans;
    int[][] g, d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    boolean[][] vis;
    int[][] q = new int[10010][2];

    void dfs(int x, int y) {
        if (x == -1 || x == n || y == -1 || y == m || vis[x][y] || g[x][y] != 1) {
            return;
        }
        vis[x][y] = true;
        q[t++] = new int[]{x, y};
        dfs(x + 1, y);
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);
    }

    public int shortestBridge(int[][] grid) {
        g = grid;
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m];
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && !flag) {
                    dfs(i, j);
                    flag = true;
                }
            }
        }
        while (h < t) {
            for (int end = t; h < end; h++) {
                var p = q[h];
                for (int i = 0; i < 4; i++) {
                    int nx = p[0] + d[i][0], ny = p[1] + d[i][1];
                    if (nx == -1 || nx == n || ny == -1 || ny == m || vis[nx][ny]) {
                        continue;
                    }
                    vis[nx][ny] = true;
                    if (grid[nx][ny] == 1) {
                        return ans;
                    }
                    q[t++] = new int[]{nx, ny};
                }
            }
            ans++;
        }
        return ans;
    }
}
